﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Runtime.InteropServices;
using System.Runtime.ConstrainedExecution;

namespace Tsanie.Image2Cmt {
    class Hash<T> : IDisposable {

        private IEqualityComparer<T> m_comparer;
        private int m_lastIndex;
        private int m_count;
        private int m_freeList;
        private int[] m_buckets;
        private Slot<T>[] m_slots;

        public Hash() {
            this.m_comparer = EqualityComparer<T>.Default;
            this.m_lastIndex = 0;
            this.m_count = 0;
            this.m_freeList = -1;
        }

        #region - public methods -

        public int AddOrGetLocation(T value) {
            int freeList;
            if (this.m_buckets == null) {
                this.Initialize(0);
            }
            int hashCode = this.InternalGetHashCode(value);
            int index = hashCode % this.m_buckets.Length;
            for (int i = this.m_buckets[hashCode % this.m_buckets.Length] - 1; i >= 0; i = this.m_slots[i].next) {
                if ((this.m_slots[i].hashCode == hashCode) && m_comparer.Equals(this.m_slots[i].value, value)) {
                    return i;
                }
            }
            if (this.m_freeList >= 0) {
                freeList = this.m_freeList;
                this.m_freeList = this.m_slots[freeList].next;
            } else {
                if (this.m_lastIndex == this.m_slots.Length) {
                    this.IncreaseCapacity();
                    index = hashCode % this.m_buckets.Length;
                }
                freeList = this.m_lastIndex;
                this.m_lastIndex++;
            }
            this.m_slots[freeList].hashCode = hashCode;
            this.m_slots[freeList].value = value;
            this.m_slots[freeList].next = this.m_buckets[index] - 1;
            this.m_buckets[index] = freeList + 1;
            this.m_count++;
            return freeList;
        }
        public bool Contains(T item) {
            if (this.m_buckets != null) {
                int hashCode = this.InternalGetHashCode(item);
                for (int i = this.m_buckets[hashCode % this.m_buckets.Length] - 1; i >= 0; i = this.m_slots[i].next) {
                    if ((this.m_slots[i].hashCode == hashCode) && m_comparer.Equals(this.m_slots[i].value, item)) {
                        return true;
                    }
                }
            }
            return false;
        }
        public Histogram<T>[] ToHistogram() {
            Histogram<T>[] array = new Histogram<T>[m_count];
            int num = 0;
            for (int i = 0; (i < this.m_lastIndex) && (num < m_count); i++) {
                if (this.m_slots[i].hashCode >= 0) {
                    array[num++].value = this.m_slots[i].value;
                }
            }
            return array;
        }

        #endregion

        #region - private methods -

        private void IncreaseCapacity() {
            int min = this.m_count * 2;
            if (min < 0) {
                min = this.m_count;
            }
            int prime = HashHelpers.GetPrime(min);
            if (prime <= this.m_count) {
                throw new ArgumentException("Arg_HSCapacityOverflow");
            }
            Slot<T>[] destinationArray = new Slot<T>[prime];
            if (this.m_slots != null) {
                Array.Copy(this.m_slots, 0, destinationArray, 0, this.m_lastIndex);
            }
            int[] numArray = new int[prime];
            for (int i = 0; i < this.m_lastIndex; i++) {
                int index = destinationArray[i].hashCode % prime;
                destinationArray[i].next = numArray[index] - 1;
                numArray[index] = i + 1;
            }
            this.m_slots = destinationArray;
            this.m_buckets = numArray;
        }
        private void Initialize(int capacity) {
            int prime = HashHelpers.GetPrime(capacity);
            this.m_buckets = new int[prime];
            this.m_slots = new Slot<T>[prime];
        }
        private int InternalGetHashCode(T item) {
            if (item == null) {
                return 0;
            }
            return (m_comparer.GetHashCode(item) & 0x7fffffff);
        }

        #endregion

        #region - IDisposable Members -

        public void Dispose() {
            m_buckets = null;
            m_slots = null;
        }

        #endregion

        [StructLayout(LayoutKind.Sequential)]
        internal struct Slot<V> {
            internal int hashCode;
            internal V value;
            internal int next;
        }
        internal static class HashHelpers {
            // Fields
            internal static readonly int[] primes;

            // Methods
            static HashHelpers() {
                primes = new int[] { 
                    3, 7, 11, 0x11, 0x17, 0x1d, 0x25, 0x2f, 0x3b, 0x47, 0x59, 0x6b, 0x83, 0xa3, 0xc5, 0xef, 
                    0x125, 0x161, 0x1af, 0x209, 0x277, 0x2f9, 0x397, 0x44f, 0x52f, 0x63d, 0x78b, 0x91d, 0xaf1, 0xd2b, 0xfd1, 0x12fd, 
                    0x16cf, 0x1b65, 0x20e3, 0x2777, 0x2f6f, 0x38ff, 0x446f, 0x521f, 0x628d, 0x7655, 0x8e01, 0xaa6b, 0xcc89, 0xf583, 0x126a7, 0x1619b, 
                    0x1a857, 0x1fd3b, 0x26315, 0x2dd67, 0x3701b, 0x42023, 0x4f361, 0x5f0ed, 0x72125, 0x88e31, 0xa443b, 0xc51eb, 0xec8c1, 0x11bdbf, 0x154a3f, 0x198c4f, 
                    0x1ea867, 0x24ca19, 0x2c25c1, 0x34fa1b, 0x3f928f, 0x4c4987, 0x5b8b6f, 0x6dda89
                 };
            }

            internal static int GetMinPrime() {
                return primes[0];
            }

            [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
            internal static int GetPrime(int min) {
                for (int i = 0; i < primes.Length; i++) {
                    int num2 = primes[i];
                    if (num2 >= min) {
                        return num2;
                    }
                }
                for (int j = min | 1; j < 0x7fffffff; j += 2) {
                    if (IsPrime(j)) {
                        return j;
                    }
                }
                return min;
            }

            [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
            internal static bool IsPrime(int candidate) {
                if ((candidate & 1) == 0) {
                    return (candidate == 2);
                }
                int num = (int)Math.Sqrt((double)candidate);
                for (int i = 3; i <= num; i += 2) {
                    if ((candidate % i) == 0) {
                        return false;
                    }
                }
                return true;
            }
        }
    }
}
